'''
给定一个简易迷宫，1 为墙，0 为通路，玩家为 %
找出迷宫的路径，并把路径上的 0 设为 #，并输出修改后的矩阵
'''
import random


def print2D(lists):
    for row in lists:
        print(row)
    print()


# Maze
def SolveMaze(maze, x, y):
    assert x >= 0 and x < len(maze)
    assert y >= 0 and y < len(maze[0])
    m, n = len(maze), len(maze[0])
    
    visited = []
    for i in range(m):
        row = []
        for j in range(n):
            row.append({'value': maze[i][j], 'prev': None})
        visited.append(row)
    
    maze[x][y] = 0
    queue = [(x, y)]

    # BFS
    for pos in queue:
        i, j = pos[0], pos[1]
        visited[i][j]['value'] = 2
        if i-1 >= 0 and maze[i-1][j] == 0 and visited[i-1][j]['value'] == 0 and (i-1, j) not in queue:
            queue.append((i-1, j))
            visited[i-1][j]['prev'] = (i, j)
        if i+1 <  m and maze[i+1][j] == 0 and visited[i+1][j]['value'] == 0 and (i+1, j) not in queue:
            queue.append((i+1, j))
            visited[i+1][j]['prev'] = (i, j)
        if j-1 >= 0 and maze[i][j-1] == 0 and visited[i][j-1]['value'] == 0 and (i, j-1) not in queue:
            queue.append((i, j-1))
            visited[i][j-1]['prev'] = (i, j)
        if j+1 <  n and maze[i][j+1] == 0 and visited[i][j+1]['value'] == 0 and (i, j+1) not in queue:
            queue.append((i, j+1))
            visited[i][j+1]['prev'] = (i, j)
            
    def trackback(node):
        while node:
            maze[node[0]][node[1]] = '#'
            node = visited[node[0]][node[1]]['prev']
    
    # Track back
    for i in [0, m-1]:
        for j in range(n):
            if visited[i][j]['value'] == 2:
                trackback((i, j))
    for j in [0, n-1]:
        for i in range(m):
            if visited[i][j]['value'] == 2:
                trackback((i, j))
    maze[x][y] = '%'  # 重置起始点为 %
    return maze


# Test
size = 8
maze = [[0 for _ in range(size)] for _ in range(size)]
for x in range(size):
    for y in range(size):
        maze[x][y] = random.choice([0, 1])
x0, y0 = 3, 3
maze[x0][y0] = '%'

print2D(maze)
SolveMaze(maze, x0, y0)
print2D(maze)
